{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://img.kaikeba.com/web/kkb_index/img_index_logo.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lesson-02 Assignment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "   本周课程主要包含了图像基本操作中的卷积/滤波，以及最基础的特征描述算法————Harris Corner和SIFT。希望大家认真复习，理解图像求导/卷积的目的，以及特征的本质。\n",
    "   本次作业分为阅读部分和算法部分。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 本次作业的内容"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Reading]:\n",
    "\n",
    "You needn't finish reading all of them in just one week!\n",
    "It's just good for you to know what's happening in this area and to figure out how people try to improve SIFT.\n",
    "\n",
    "You needn't to remember all of them. \n",
    "But please DO REMEMBER procedures of SIFT and HoG. For those who're interested in SLAM, Orb is your inevitable destiny.\n",
    "\n",
    "1. [optional] Bilateral Filter: https://blog.csdn.net/piaoxuezhong/article/details/78302920\n",
    "2. Feature Descriptors:\n",
    "   [Compulsory]\n",
    "   Hog: https://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf\n",
    "   SURF: https://www.vision.ee.ethz.ch/~surf/eccv06.pdf\n",
    "   [optional]\n",
    "   BRISK: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.371.1343&rep=rep1&type=pdf\n",
    "   Orb: http://www.willowgarage.com/sites/default/files/orb_final.pdf [Compulsory for SLAM Guys]\n",
    "3. Preview parts:\n",
    "   K-Means: I have no doubts about what you are going to read and where you gonna find the reading materials. There are tons of papers/blogs describing k-means. Just grab one and read.We'll talk about this topic in 3 weeks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Coding]:\n",
    "Finish 2D convolution/filtering by your self. \n",
    "What you are supposed to do can be described as \"median blur\", which means by using a sliding window on an image, your task is not going to do a normal convolution, but to find the median value within that crop.\n",
    "\n",
    "You can assume your input has only one channel. (a.k.a a normal 2D list/vector) And you do need to consider the padding method and size. There are 2 padding ways: REPLICA & ZERO. When \"REPLICA\" is given to you, the padded pixels are same with the border pixels. E.g is [1 2 3] is your image, the padded version will be  [[(...1 1) 1 2 3 (3 3...)]  where how many 1 & 3 in the parenthesis depends on your padding size. When \"ZERO\", the padded version will be [(...0 0) 1 2 3 (0 0...)]\n",
    "\n",
    "Assume your input's size of the image is W x H, kernel size's m x n. You may first complete a version with O(W·H·m·n log(m·n)) to O(W·H·m·n·m·n)).\n",
    "\n",
    "Follow up 1: Can it be completed in a shorter time complexity?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mid_trans(channel, kernel_size, fill=0):\n",
    "    total_length = kernel_size * kernel_size\n",
    "    offset = kernel_size // 2\n",
    "    source = channel.copy()\n",
    "    y_length, x_length = source.shape\n",
    "    for y_index in range(y_length):\n",
    "        for x_index in range(x_length):\n",
    "            x_start = x_index - 1\n",
    "            y_start = y_index - 1\n",
    "            x_start = x_index if x_start < 0 else x_start\n",
    "            y_start = y_index if y_start < 0 else y_start\n",
    "            x_end = min(x_length, x_index + offset + 1)\n",
    "            y_end = min(y_length, y_index + offset + 1)\n",
    "            data = channel[y_start:y_end, x_start:x_end].ravel()\n",
    "            add_zero = total_length - len(data)\n",
    "            # 补0\n",
    "            for _ in range(add_zero):\n",
    "                data = np.append(data, fill)\n",
    "            mid_value = np.median(data)\n",
    "            source[y_index,x_index] = mid_value\n",
    "    return source\n",
    "\n",
    "def mediaBlur(image, to_rgb=None, kernel_size=3, fill=0):\n",
    "    if to_rgb is not None:\n",
    "        image = cv2.cvtColor(image, to_rgb)\n",
    "    \n",
    "    rc, gc, bc = cv2.split(image)\n",
    "    mid_r = mid_trans(rc, kernel_size, fill)\n",
    "    mid_g = mid_trans(gc, kernel_size, fill)\n",
    "    mid_b = mid_trans(bc, kernel_size, fill)\n",
    "    return cv2.merge((mid_r, mid_g, mid_b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Reading + Pseudo Code]:\n",
    "We haven't told RANSAC algorithm this week. So please try to do the reading.\n",
    "\n",
    "And now, we can describe it here:\n",
    "    We have 2 sets of points, say, Points A and Points B. We use A.1 to denote the first point in A, B.2 the 2nd point in B and so forth. Ideally, A.1 is corresponding to B.1, ... A.m corresponding B.m. However, it's obvious that the matching cannot be so perfect and the matching in our real world is like: \n",
    "    A.1-B.13, A.2-B.24, A.3-x (has no matching), x-B.5, A.4-B.24(This is a wrong matching) ...\n",
    "    The target of RANSAC is to find out the true matching within this messy.\n",
    "    \n",
    "Algorithm for this procedure can be described like this:\n",
    "    1. Choose 4 pair of points randomly in our matching points. Those four called \"inlier\" (中文： 内点) while others \"outlier\" (中文： 外点)\n",
    "    2. Get the homography of the inliers\n",
    "    3. Use this computed homography to test all the other outliers. And separated them by using a threshold into two parts:\n",
    "        a. new inliers which is satisfied our computed homography\n",
    "        b. new outliers which is not satisfied by our computed homography.\n",
    "    4. Get our all inliers (new inliers + old inliers) and goto step 2\n",
    "    5. As long as there's no changes or we have already repeated step 2-4 k, a number actually can be computed, times, we jump out of the recursion. The final homography matrix will be the one that we want.\n",
    "\n",
    "[WARNING!!! RANSAC is a general method. Here we add our matching background to that.]\n",
    "\n",
    "Your task: please complete pseudo code (it would be great if you hand in real code!) of this procedure.\n",
    "\n",
    "Python:\n",
    "def ransacMatching(A, B):\n",
    "    A & B: List of List\n",
    "\n",
    "Follow up 1. For step 3. How to do the \"test“? Please clarify this in your code/pseudo code\n",
    "Follow up 2. How do decide the \"k\" mentioned in step 5. Think about it mathematically!\n",
    "\n",
    "You are supposed to hand in the code in 1 week."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# RANSAC伪代码：\n",
    "## 1. 选取部分特征点，并初始化模型\n",
    "$$\n",
    "\\Large f(X_0) \\Rightarrow Y_0\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 根据误差，对各点进行分类\n",
    "- 误差: $\\Large \\epsilon$\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{matrix}\n",
    "f(x_i) - Y_i > \\epsilon & false \\\\\n",
    "f(x_i) - Y_i \\le \\epsilon & true\n",
    "\\end{matrix}\n",
    "\\right.\n",
    "$$\n",
    "\n",
    "记录命中的值，也就是$true$的点的分类。不要忘记第一步中选取的初始化点哦。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 判断和返回\n",
    "- 迭代次数：$N$\n",
    "\n",
    "步骤如下\n",
    "\n",
    "- 如果不满足迭代次数，更新最多命中模型(点集)，然后到第一步重复执行\n",
    "- 达到迭代次数，返回最多命中模型(点集合)，如果都没有，返回none\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```python\n",
    "def mapping(X, Y, times, threshold, want):\n",
    "    result = []\n",
    "    _times = 0\n",
    "    while len(result) < want or _times < times:\n",
    "        sample_x, sample_y = choose_sample(X, Y)\n",
    "        sample_func = get_sanple_function(sample_x, sample_y)\n",
    "        result = np.append(result, (sample_func, len(sample_func(X)[sample_func(X) - Y < threshold])))\n",
    "    return None if not result else np.sort(result)[-1]\n",
    "                           \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [作业截止时间]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "作业能帮助你回顾课堂内容，你又可以通过作业进行代码实操。咱们可要认真、及时的完成作业哦！自布置作业起两周内提交，助教及时批改作业哦～逾期提交不批改。（特殊情况，请找班主任请假。）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这次的作业就到这里了！祝大家学习进步！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image alt <](http://5b0988e595225.cdn.sohucs.com/images/20190420/1d1070881fd540db817b2a3bdd967f37.gif)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
